As is known in the art, an image processing system is often used to translate and feed input signals representative of an image in an input device to output signals representative of that same image in an output image. For example, a video camera may register a given input image, which is subsequently transferred to an output device, such as a video screen, or a printer. Often the input device may have a greater capacity to represent the different colors or gray scale shades of the input image than the output device. If the input device can represent more colors than the output device, an image processing system may be employed for converting the greater number of input colors to a lesser number of output colors, to make the output image appear as visually similar to the input image as possible. Four such methods of converting input images to output images are 1) histogram based methods, 2) chrominance subsampling, 3) hardware color mixing, and 4) dithering.
With a histogram based technique, a processor is used to collect histogram statistics on the input image data, and the statistical information is used to compensate the image data. Thus, the histogram technique requires two passes of the entire input image data; the first to acquire the histogram statistics and the second to compensate the data. This results in a system which has the drawback of being too slow for those applications in which speed is important. In addition, in cases where the colors change gradually over a wide area, considerable contouring of the image can occur, resulting in a less desirable output image.
Chrominance subsampling, on the other hand, typically requires specialized hardware, such as unconventional frame buffers and very fast and expensive upscaling and color space conversion hardware. Due to the unique hardware requirements of the chrominance subsampling technique, it is not practical to implement in a general computing environment. In addition, the image quality suffers in areas of high chrominance detail.
The third technique, hardware color mixing, requires that the image data must be preprocessed off line with a multiple pass algorithm. Thus, like the histogram based technique, this approach is also slow. Additionally, the resulting image file is device dependent, resulting in the requirement of unique hardware, a drawback similar to that of the chrominance subsampling technique.
The fourth technique for converting the greater number of input colors to a lesser number of output colors, dithering, is based on using the available set of output colors in a judicious arrangement so that the illusion of a greater number of output colors is provided. Additionally, the arrangement of the output colors through the dithering technique is designed to assure that a pleasing output image is produced.
One such dithering technique is reported in Ulichney, R. "Digital Halftoning" The MIT Press (1987), hereinafter referred to as "Ulichney". In Ulichney, equation 9.5 provides the following: EQU I.sub.K &lt;x,y&gt;=&lt;1/(2.sup.K -1)&gt;&lt;int{&lt;(2.sup.K -1) J&lt;x,y&gt;&gt;+D&lt;x,y&gt;}&gt;
where:
I.sub.K &lt;x,y&gt; is the output value of the image at position x,y of the output image; PA1 K is the number of bits used to represent the output value I&lt;x,y&gt;; PA1 J&lt;x,y&gt; is the input value of the image at position x,y of the input image, normalized to a range between 0 and 1; PA1 D&lt;x,y&gt; is the dither matrix value at position x,y of the dither matrix, normalized to a range between 0 and 1; PA1 int{x} is a truncate function in which after any mathematical operations within the brackets are performed and a final value is determined, any amount remaining after the decimal point is truncated so that the remaining value is an integer. For example, int{5.3}=5, and int{27.999}=27;
One drawback to this dithering approach is that the equation only permits dithering to powers of 2, rather than any number. Also, the equation requires that the input must be scaled to a range between 0 and 1, but does not give any indication of how that scaling is to be done, or how the values of the dither matrix are to be spaced to achieve symmetric dithering.